package sf;

import java.util.Arrays;

/**
 * 描述
 *
 * @author lgb
 * @date 2020/08/30
 **/
public class KmpSearch {

    private int[] toPattern(String word) {
        int[] p = new int[word.length()];
        Arrays.fill(p, -1);
        for (int i = 1; i < word.length(); i++) {
            int j = p[i - 1];
            while (j != -1 && word.charAt(j + 1) != word.charAt(i)) {
                j = p[j];
            }
            if (word.charAt(i) == word.charAt(j + 1)) {
                p[i] = j + 1;
            }
        }
        return p;
    }

    /**
     * 获取word在content中的位置
     *
     * @param content 内容
     * @param word 匹配串
     * @return 索引
     */
    public int search(String content, String word) {
        int[] p = toPattern(word);
        int i = 0, j = -1;
        while (i < content.length() && j < word.length() - 1) {
            if (content.charAt(i) == word.charAt(j + 1)) {
                i ++;
                j ++;
            } else {
                j = p[j];
            }
        }
        if (j != word.length() - 1) {// 肯定没找到
            return -1;
        }
        return i - word.length();
    }



    public static void main(String[] args) {
        KmpSearch kmpSearch = new KmpSearch();
        int search = kmpSearch.search("ababcabcd", "abc");
        System.out.println(search);
    }

}
